package LBLD新算法;

import org.junit.Test;

import java.util.*;

/*
    每个节点只处理自己（单cur思想）
    做完题一定写入表格
*/
/*
    输入：
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
输出：[null,null,null,null,null,null,null,5,7,5,4]
解释：
执行六次 .push 操作后，栈自底向上为 [5,7,5,7,4,5]。然后：

pop() -> 返回 5，因为 5 是出现频率最高的。
栈变成 [5,7,5,7,4]。

pop() -> 返回 7，因为 5 和 7 都是频率最高的，但 7 最接近栈顶。
栈变成 [5,7,5,4]。

pop() -> 返回 5 。
栈变成 [5,7,4]。

pop() -> 返回 4 。
栈变成 [5,7]。

*/
public class 最大频率栈895 {
    /*
        max不要记录最大个数的val
        而是记录最大个数maxGeshu
    */
    class FreqStack {
        int maxGeshu = 0;
        Map<Integer, Integer> geshu = new HashMap<>();
        Map<Integer, Stack<Integer>> geshuZhan = new HashMap<>();
        public FreqStack() {}

        public void push(int val) {
            //个数map
            geshu.put(val, geshu.getOrDefault(val,0)+1);
            //个数栈map
            int curGeshu = geshu.get(val);
            Stack<Integer> s = geshuZhan.get(curGeshu);
            if(s==null){
                Stack<Integer> newS = new Stack<>();
                newS.push(val);
                geshuZhan.put(curGeshu, newS);
            }else{
                geshuZhan.get(curGeshu).push(val);
            }
            //全局max
            if(curGeshu>maxGeshu){
                maxGeshu=curGeshu;
            }
        }

        public int pop() {
            //(取max
            //个数栈弹出
            Stack<Integer> s = geshuZhan.get(maxGeshu);
            Integer pop = s.pop();
            //个数map-1
            geshu.put(pop, geshu.get(pop)-1);
            //缺：看看max个数的栈是否空了，空了就要最大个数-1
            if(s.isEmpty()){
                maxGeshu--;
            }
            return pop;
        }
    }

    @Test
    public void test() {
        FreqStack s = new FreqStack();
        s.push(5);
        s.push(7);
        s.push(5);
        s.push(7);
        s.push(4);
        s.push(5);
        System.out.println(s.pop());//5
        System.out.println(s.pop());//7
        System.out.println(s.pop());//5
        System.out.println(s.pop());//4
    }
}
